#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long sum = 0, upperlim = 1;

void test(long row, long ld, long rd)
{

    if (row != upperlim)
    {
        // upperlim表示所有column位
        // row表示各行已经被填充的column位；ld、rd表示在其他皇后斜线上的column位
        // pos表示可能填充的column位
        long pos = upperlim & ~(row | ld | rd);
        while (pos)
        {
            // 补码表示法规定：正数的补码与原码相同，负数的补码为对该数的原码除符号位外各位取反，然后在最后一位加1.2015年3月6日
            // 这里p指从右到左，第一个1所在的位数，这里指尝试第一个位数
            long p = pos & -pos;

            // 这里指从pos可能的column位中，拿掉要尝试的column位
            pos -= p;
            test(row + p, (ld + p) << 1, (rd + p) >> 1);
        }
    }
    else
        sum++;
}

int main(int argc, char *argv[])
{
    time_t tm;
    int n = 16;

    if (argc != 1)
        n = atoi(argv[1]);

    tm = time(0);
    if ((n < 1) || (n > 32))
    {
        printf(" 只能计算1-32之间\n");
        exit(-1);
    }
    printf("%d 皇后\n", n);
    // upperlim 以二进制的形式表示行遍历标志，如5行全部遍历为 b11111 = 0x1f，此时依旧没有attack表示发现一种解法
    upperlim = (upperlim << n) - 1;

    test(0, 0, 0);
    printf("共有%ld种排列, 计算时间%d秒 \n", sum, (int)(time(0) - tm));
}